Home > Search Results: keywords:"analysis by reduction"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
Restricted Restarting Automata
 Černo, Peter ; Mráz, František (advisor) ; Kutrib, Martin (referee) ; Průša, Daniel (referee)
Restarting automata were introduced as a model for analysis by reduction which is a linguistically motivated method for checking correctness of a sentence. The thesis studies locally restricted models of restarting automata which (to the contrary of general restarting automata) can modify the input tape based only on a limited context. The investigation of such restricted models is easier than in the case of general restarting automata. Moreover, these models are effectively learnable from positive samples of reductions and their instructions are human readable. Powered by TCPDF (www.tcpdf.org)
Detailed record
Machine learning of analysis by reduction
 Hoffmann, Petr ; Mráz, František (advisor) ; Otto, Friedrich (referee) ; Průša, Daniel (referee)
We study the inference of models of the analysis by reduction that forms an important tool for parsing natural language sentences. We prove that the inference of such models from positive and negative samples is NP-hard when requiring a small model. On the other hand, if only positive samples are considered, the problem is effectively solvable. We propose a new model of the analysis by reduction (the so-called single k-reversible restarting automaton) and propose a method for inferring it from positive samples of analyses by reduction. The power of the model lies between growing context-sensitive languages and context-sensitive languages. Benchmarks using targets based on grammars have several drawbacks. Therefore we propose a benchmark working with targets based on random automata, that can be used to evaluate inference algorithms. This benchmark is then used to evaluate our inference method. 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English